home *** CD-ROM | disk | FTP | other *** search
/ Software of the Month Club 2000 October / Software of the Month - Ultimate Collection Shareware 277.iso / pc / PROGRAMS / UTILITY / WINLINUX / DATA1.CAB / programs_-_kernel_source / KERNEL / SCHED.C < prev    next >
C/C++ Source or Header  |  1999-09-17  |  48KB  |  1,955 lines
  1. /*
  2.  *  linux/kernel/sched.c
  3.  *
  4.  *  Copyright (C) 1991, 1992  Linus Torvalds
  5.  *
  6.  *  1996-12-23  Modified by Dave Grothe to fix bugs in semaphores and
  7.  *              make semaphores SMP safe
  8.  *  1997-01-28  Modified by Finn Arne Gangstad to make timers scale better.
  9.  *  1997-09-10    Updated NTP code according to technical memorandum Jan '96
  10.  *        "A Kernel Model for Precision Timekeeping" by Dave Mills
  11.  *  1998-11-19    Implemented schedule_timeout() and related stuff
  12.  *        by Andrea Arcangeli
  13.  *  1998-12-24    Fixed a xtime SMP race (we need the xtime_lock rw spinlock to
  14.  *        serialize accesses to xtime/lost_ticks).
  15.  *                Copyright (C) 1998  Andrea Arcangeli
  16.  *  1998-12-28  Implemented better SMP scheduling by Ingo Molnar
  17.  *  1999-03-10    Improved NTP compatibility by Ulrich Windl
  18.  */
  19.  
  20. /*
  21.  * 'sched.c' is the main kernel file. It contains scheduling primitives
  22.  * (sleep_on, wakeup, schedule etc) as well as a number of simple system
  23.  * call functions (type getpid()), which just extract a field from
  24.  * current-task
  25.  */
  26.  
  27. #include <linux/mm.h>
  28. #include <linux/kernel_stat.h>
  29. #include <linux/fdreg.h>
  30. #include <linux/delay.h>
  31. #include <linux/interrupt.h>
  32. #include <linux/smp_lock.h>
  33. #include <linux/init.h>
  34.  
  35. #include <asm/io.h>
  36. #include <asm/uaccess.h>
  37. #include <asm/pgtable.h>
  38. #include <asm/mmu_context.h>
  39. #include <asm/semaphore-helper.h>
  40.  
  41. #include <linux/timex.h>
  42.  
  43. /*
  44.  * kernel variables
  45.  */
  46.  
  47. unsigned securebits = SECUREBITS_DEFAULT; /* systemwide security settings */
  48.  
  49. long tick = (1000000 + HZ/2) / HZ;    /* timer interrupt period */
  50.  
  51. /* The current time */
  52. volatile struct timeval xtime __attribute__ ((aligned (16)));
  53.  
  54. /* Don't completely fail for HZ > 500.  */
  55. int tickadj = 500/HZ ? : 1;        /* microsecs */
  56.  
  57. DECLARE_TASK_QUEUE(tq_timer);
  58. DECLARE_TASK_QUEUE(tq_immediate);
  59. DECLARE_TASK_QUEUE(tq_scheduler);
  60.  
  61. /*
  62.  * phase-lock loop variables
  63.  */
  64. /* TIME_ERROR prevents overwriting the CMOS clock */
  65. int time_state = TIME_OK;    /* clock synchronization status */
  66. int time_status = STA_UNSYNC;    /* clock status bits */
  67. long time_offset = 0;        /* time adjustment (us) */
  68. long time_constant = 2;        /* pll time constant */
  69. long time_tolerance = MAXFREQ;    /* frequency tolerance (ppm) */
  70. long time_precision = 1;    /* clock precision (us) */
  71. long time_maxerror = NTP_PHASE_LIMIT;    /* maximum error (us) */
  72. long time_esterror = NTP_PHASE_LIMIT;    /* estimated error (us) */
  73. long time_phase = 0;        /* phase offset (scaled us) */
  74. long time_freq = ((1000000 + HZ/2) % HZ - HZ/2) << SHIFT_USEC;    /* frequency offset (scaled ppm) */
  75. long time_adj = 0;        /* tick adjust (scaled 1 / HZ) */
  76. long time_reftime = 0;        /* time at last adjustment (s) */
  77.  
  78. long time_adjust = 0;
  79. long time_adjust_step = 0;
  80.  
  81. unsigned long event = 0;
  82.  
  83. extern int do_setitimer(int, struct itimerval *, struct itimerval *);
  84. unsigned int * prof_buffer = NULL;
  85. unsigned long prof_len = 0;
  86. unsigned long prof_shift = 0;
  87.  
  88. extern void mem_use(void);
  89.  
  90. unsigned long volatile jiffies=0;
  91.  
  92. /*
  93.  *    Init task must be ok at boot for the ix86 as we will check its signals
  94.  *    via the SMP irq return path.
  95.  */
  96.  
  97. struct task_struct * task[NR_TASKS] = {&init_task, };
  98.  
  99. struct kernel_stat kstat = { 0 };
  100.  
  101. void scheduling_functions_start_here(void) { }
  102.  
  103. #ifdef __SMP__
  104. static void reschedule_idle_slow(struct task_struct * p)
  105. {
  106. /*
  107.  * (see reschedule_idle() for an explanation first ...)
  108.  *
  109.  * Pass #2
  110.  *
  111.  * We try to find another (idle) CPU for this woken-up process.
  112.  *
  113.  * On SMP, we mostly try to see if the CPU the task used
  114.  * to run on is idle.. but we will use another idle CPU too,
  115.  * at this point we already know that this CPU is not
  116.  * willing to reschedule in the near future.
  117.  *
  118.  * An idle CPU is definitely wasted, especially if this CPU is
  119.  * running long-timeslice processes. The following algorithm is
  120.  * pretty good at finding the best idle CPU to send this process
  121.  * to.
  122.  *
  123.  * [We can try to preempt low-priority processes on other CPUs in
  124.  * 2.3. Also we can try to use the avg_slice value to predict
  125.  * 'likely reschedule' events even on other CPUs.]
  126.  */
  127.     int best_cpu = p->processor, this_cpu = smp_processor_id();
  128.     struct task_struct **idle = task, *tsk, *target_tsk;
  129.     int i = smp_num_cpus;
  130.  
  131.     target_tsk = NULL;
  132.     do {
  133.         tsk = *idle;
  134.         idle++;
  135.         if (tsk->has_cpu) {
  136.             if (tsk->processor == this_cpu)
  137.                 continue;
  138.             target_tsk = tsk;
  139.             if (tsk->processor == best_cpu) {
  140.                 /*
  141.                  * bingo, we couldnt get a better
  142.                  * CPU, activate it.
  143.                  */
  144.                 goto send; /* this one helps GCC ... */
  145.             }
  146.         }
  147.     } while (--i > 0);
  148.  
  149.     /*
  150.      * found any idle CPU?
  151.      */
  152.     if (target_tsk) {
  153. send:
  154.         target_tsk->need_resched = 1;
  155.         smp_send_reschedule(target_tsk->processor);
  156.         return;
  157.     }
  158. }
  159. #endif /* __SMP__ */
  160.  
  161. /*
  162.  * If there is a dependency between p1 and p2,
  163.  * don't be too eager to go into the slow schedule.
  164.  * In particular, if p1 and p2 both want the kernel
  165.  * lock, there is no point in trying to make them
  166.  * extremely parallel..
  167.  *
  168.  * (No lock - lock_depth < 0)
  169.  */
  170. #define related(p1,p2) ((p1)->lock_depth >= 0 && (p2)->lock_depth >= 0)
  171.  
  172. static inline void reschedule_idle(struct task_struct * p)
  173. {
  174.  
  175.     if (p->policy != SCHED_OTHER || p->counter > current->counter + 3) {
  176.         current->need_resched = 1;
  177.         return;
  178.     }
  179.  
  180. #ifdef __SMP__
  181.     /*
  182.      * ("wakeup()" should not be called before we've initialized
  183.      * SMP completely.
  184.      * Basically a not-yet initialized SMP subsystem can be
  185.      * considered as a not-yet working scheduler, simply dont use
  186.      * it before it's up and running ...)
  187.      *
  188.      * SMP rescheduling is done in 2 passes:
  189.      *  - pass #1: faster: 'quick decisions'
  190.      *  - pass #2: slower: 'lets try and find another CPU'
  191.      */
  192.  
  193.     /*
  194.      * Pass #1
  195.      *
  196.      * There are two metrics here:
  197.      *
  198.      * first, a 'cutoff' interval, currently 0-200 usecs on
  199.      * x86 CPUs, depending on the size of the 'SMP-local cache'.
  200.      * If the current process has longer average timeslices than
  201.      * this, then we utilize the idle CPU.
  202.      *
  203.      * second, if the wakeup comes from a process context,
  204.      * then the two processes are 'related'. (they form a
  205.      * 'gang')
  206.      *
  207.      * An idle CPU is almost always a bad thing, thus we skip
  208.      * the idle-CPU utilization only if both these conditions
  209.      * are true. (ie. a 'process-gang' rescheduling with rather
  210.      * high frequency should stay on the same CPU).
  211.      *
  212.      * [We can switch to something more finegrained in 2.3.]
  213.      */
  214.     if ((current->avg_slice < cacheflush_time) && related(current, p))
  215.         return;
  216.  
  217.     reschedule_idle_slow(p);
  218. #endif /* __SMP__ */
  219. }
  220.  
  221. /*
  222.  * Careful!
  223.  *
  224.  * This has to add the process to the _beginning_ of the
  225.  * run-queue, not the end. See the comment about "This is
  226.  * subtle" in the scheduler proper..
  227.  */
  228. static inline void add_to_runqueue(struct task_struct * p)
  229. {
  230.     struct task_struct *next = init_task.next_run;
  231.  
  232.     p->prev_run = &init_task;
  233.     init_task.next_run = p;
  234.     p->next_run = next;
  235.     next->prev_run = p;
  236.     nr_running++;
  237. }
  238.  
  239. static inline void del_from_runqueue(struct task_struct * p)
  240. {
  241.     struct task_struct *next = p->next_run;
  242.     struct task_struct *prev = p->prev_run;
  243.  
  244.     nr_running--;
  245.     next->prev_run = prev;
  246.     prev->next_run = next;
  247.     p->next_run = NULL;
  248.     p->prev_run = NULL;
  249. }
  250.  
  251. static inline void move_last_runqueue(struct task_struct * p)
  252. {
  253.     struct task_struct *next = p->next_run;
  254.     struct task_struct *prev = p->prev_run;
  255.  
  256.     /* remove from list */
  257.     next->prev_run = prev;
  258.     prev->next_run = next;
  259.     /* add back to list */
  260.     p->next_run = &init_task;
  261.     prev = init_task.prev_run;
  262.     init_task.prev_run = p;
  263.     p->prev_run = prev;
  264.     prev->next_run = p;
  265. }
  266.  
  267. static inline void move_first_runqueue(struct task_struct * p)
  268. {
  269.     struct task_struct *next = p->next_run;
  270.     struct task_struct *prev = p->prev_run;
  271.  
  272.     /* remove from list */
  273.     next->prev_run = prev;
  274.     prev->next_run = next;
  275.     /* add back to list */
  276.     p->prev_run = &init_task;
  277.     next = init_task.next_run;
  278.     init_task.next_run = p;
  279.     p->next_run = next;
  280.     next->prev_run = p;
  281. }
  282.  
  283. /*
  284.  * The tasklist_lock protects the linked list of processes.
  285.  *
  286.  * The scheduler lock is protecting against multiple entry
  287.  * into the scheduling code, and doesn't need to worry
  288.  * about interrupts (because interrupts cannot call the
  289.  * scheduler).
  290.  *
  291.  * The run-queue lock locks the parts that actually access
  292.  * and change the run-queues, and have to be interrupt-safe.
  293.  */
  294. spinlock_t scheduler_lock = SPIN_LOCK_UNLOCKED;    /* should be acquired first */
  295. spinlock_t runqueue_lock = SPIN_LOCK_UNLOCKED;  /* second */
  296. rwlock_t tasklist_lock = RW_LOCK_UNLOCKED;    /* third */
  297.  
  298. /*
  299.  * Wake up a process. Put it on the run-queue if it's not
  300.  * already there.  The "current" process is always on the
  301.  * run-queue (except when the actual re-schedule is in
  302.  * progress), and as such you're allowed to do the simpler
  303.  * "current->state = TASK_RUNNING" to mark yourself runnable
  304.  * without the overhead of this.
  305.  */
  306. void wake_up_process(struct task_struct * p)
  307. {
  308.     unsigned long flags;
  309.  
  310.     spin_lock_irqsave(&runqueue_lock, flags);
  311.     p->state = TASK_RUNNING;
  312.     if (!p->next_run) {
  313.         add_to_runqueue(p);
  314.         reschedule_idle(p);
  315.     }
  316.     spin_unlock_irqrestore(&runqueue_lock, flags);
  317. }
  318.  
  319. static void process_timeout(unsigned long __data)
  320. {
  321.     struct task_struct * p = (struct task_struct *) __data;
  322.  
  323.     wake_up_process(p);
  324. }
  325.  
  326. /*
  327.  * This is the function that decides how desirable a process is..
  328.  * You can weigh different processes against each other depending
  329.  * on what CPU they've run on lately etc to try to handle cache
  330.  * and TLB miss penalties.
  331.  *
  332.  * Return values:
  333.  *     -1000: never select this
  334.  *         0: out of time, recalculate counters (but it might still be
  335.  *        selected)
  336.  *       +ve: "goodness" value (the larger, the better)
  337.  *     +1000: realtime process, select this.
  338.  */
  339. static inline int goodness(struct task_struct * p, struct task_struct * prev, int this_cpu)
  340. {
  341.     int policy = p->policy;
  342.     int weight;
  343.  
  344.     if (policy & SCHED_YIELD) {
  345.         p->policy = policy & ~SCHED_YIELD;
  346.         return 0;
  347.     }
  348.  
  349.     /*
  350.      * Realtime process, select the first one on the
  351.      * runqueue (taking priorities within processes
  352.      * into account).
  353.      */
  354.     if (policy != SCHED_OTHER)
  355.         return 1000 + p->rt_priority;
  356.  
  357.     /*
  358.      * Give the process a first-approximation goodness value
  359.      * according to the number of clock-ticks it has left.
  360.      *
  361.      * Don't do any other calculations if the time slice is
  362.      * over..
  363.      */
  364.     weight = p->counter;
  365.     if (weight) {
  366.             
  367. #ifdef __SMP__
  368.         /* Give a largish advantage to the same processor...   */
  369.         /* (this is equivalent to penalizing other processors) */
  370.         if (p->processor == this_cpu)
  371.             weight += PROC_CHANGE_PENALTY;
  372. #endif
  373.  
  374.         /* .. and a slight advantage to the current thread */
  375.         if (p->mm == prev->mm)
  376.             weight += 1;
  377.         weight += p->priority;
  378.     }
  379.  
  380.     return weight;
  381. }
  382.  
  383. /*
  384.  * Event timer code
  385.  */
  386. #define TVN_BITS 6
  387. #define TVR_BITS 8
  388. #define TVN_SIZE (1 << TVN_BITS)
  389. #define TVR_SIZE (1 << TVR_BITS)
  390. #define TVN_MASK (TVN_SIZE - 1)
  391. #define TVR_MASK (TVR_SIZE - 1)
  392.  
  393. struct timer_vec {
  394.         int index;
  395.         struct timer_list *vec[TVN_SIZE];
  396. };
  397.  
  398. struct timer_vec_root {
  399.         int index;
  400.         struct timer_list *vec[TVR_SIZE];
  401. };
  402.  
  403. static struct timer_vec tv5 = { 0 };
  404. static struct timer_vec tv4 = { 0 };
  405. static struct timer_vec tv3 = { 0 };
  406. static struct timer_vec tv2 = { 0 };
  407. static struct timer_vec_root tv1 = { 0 };
  408.  
  409. static struct timer_vec * const tvecs[] = {
  410.     (struct timer_vec *)&tv1, &tv2, &tv3, &tv4, &tv5
  411. };
  412.  
  413. #define NOOF_TVECS (sizeof(tvecs) / sizeof(tvecs[0]))
  414.  
  415. static unsigned long timer_jiffies = 0;
  416.  
  417. static inline void insert_timer(struct timer_list *timer,
  418.                 struct timer_list **vec, int idx)
  419. {
  420.     if ((timer->next = vec[idx]))
  421.         vec[idx]->prev = timer;
  422.     vec[idx] = timer;
  423.     timer->prev = (struct timer_list *)&vec[idx];
  424. }
  425.  
  426. static inline void internal_add_timer(struct timer_list *timer)
  427. {
  428.     /*
  429.      * must be cli-ed when calling this
  430.      */
  431.     unsigned long expires = timer->expires;
  432.     unsigned long idx = expires - timer_jiffies;
  433.  
  434.     if (idx < TVR_SIZE) {
  435.         int i = expires & TVR_MASK;
  436.         insert_timer(timer, tv1.vec, i);
  437.     } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
  438.         int i = (expires >> TVR_BITS) & TVN_MASK;
  439.         insert_timer(timer, tv2.vec, i);
  440.     } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {
  441.         int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
  442.         insert_timer(timer, tv3.vec, i);
  443.     } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {
  444.         int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
  445.         insert_timer(timer, tv4.vec, i);
  446.     } else if ((signed long) idx < 0) {
  447.         /* can happen if you add a timer with expires == jiffies,
  448.          * or you set a timer to go off in the past
  449.          */
  450.         insert_timer(timer, tv1.vec, tv1.index);
  451.     } else if (idx <= 0xffffffffUL) {
  452.         int i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
  453.         insert_timer(timer, tv5.vec, i);
  454.     } else {
  455.         /* Can only get here on architectures with 64-bit jiffies */
  456.         timer->next = timer->prev = timer;
  457.     }
  458. }
  459.  
  460. spinlock_t timerlist_lock = SPIN_LOCK_UNLOCKED;
  461.  
  462. void add_timer(struct timer_list *timer)
  463. {
  464.     unsigned long flags;
  465.  
  466.     spin_lock_irqsave(&timerlist_lock, flags);
  467.     if (timer->prev)
  468.         goto bug;
  469.     internal_add_timer(timer);
  470. out:
  471.     spin_unlock_irqrestore(&timerlist_lock, flags);
  472.     return;
  473.  
  474. bug:
  475.     printk("bug: kernel timer added twice at %p.\n",
  476.             __builtin_return_address(0));
  477.     goto out;
  478. }
  479.  
  480. static inline int detach_timer(struct timer_list *timer)
  481. {
  482.     struct timer_list *prev = timer->prev;
  483.     if (prev) {
  484.         struct timer_list *next = timer->next;
  485.         prev->next = next;
  486.         if (next)
  487.             next->prev = prev;
  488.         return 1;
  489.     }
  490.     return 0;
  491. }
  492.  
  493. void mod_timer(struct timer_list *timer, unsigned long expires)
  494. {
  495.     unsigned long flags;
  496.  
  497.     spin_lock_irqsave(&timerlist_lock, flags);
  498.     timer->expires = expires;
  499.     detach_timer(timer);
  500.     internal_add_timer(timer);
  501.     spin_unlock_irqrestore(&timerlist_lock, flags);
  502. }
  503.  
  504. int del_timer(struct timer_list * timer)
  505. {
  506.     int ret;
  507.     unsigned long flags;
  508.  
  509.     spin_lock_irqsave(&timerlist_lock, flags);
  510.     ret = detach_timer(timer);
  511.     timer->next = timer->prev = 0;
  512.     spin_unlock_irqrestore(&timerlist_lock, flags);
  513.     return ret;
  514. }
  515.  
  516. #ifdef __SMP__
  517.  
  518. #define idle_task (task[cpu_number_map[this_cpu]])
  519. #define can_schedule(p)    (!(p)->has_cpu)
  520.  
  521. #else
  522.  
  523. #define idle_task (&init_task)
  524. #define can_schedule(p) (1)
  525.  
  526. #endif
  527.  
  528. signed long schedule_timeout(signed long timeout)
  529. {
  530.     struct timer_list timer;
  531.     unsigned long expire;
  532.  
  533.     switch (timeout)
  534.     {
  535.     case MAX_SCHEDULE_TIMEOUT:
  536.         /*
  537.          * These two special cases are useful to be comfortable
  538.          * in the caller. Nothing more. We could take
  539.          * MAX_SCHEDULE_TIMEOUT from one of the negative value
  540.          * but I' d like to return a valid offset (>=0) to allow
  541.          * the caller to do everything it want with the retval.
  542.          */
  543.         schedule();
  544.         goto out;
  545.     default:
  546.         /*
  547.          * Another bit of PARANOID. Note that the retval will be
  548.          * 0 since no piece of kernel is supposed to do a check
  549.          * for a negative retval of schedule_timeout() (since it
  550.          * should never happens anyway). You just have the printk()
  551.          * that will tell you if something is gone wrong and where.
  552.          */
  553.         if (timeout < 0)
  554.         {
  555.             printk(KERN_ERR "schedule_timeout: wrong timeout "
  556.                    "value %lx from %p\n", timeout,
  557.                    __builtin_return_address(0));
  558.             goto out;
  559.         }
  560.     }
  561.  
  562.     expire = timeout + jiffies;
  563.  
  564.     init_timer(&timer);
  565.     timer.expires = expire;
  566.     timer.data = (unsigned long) current;
  567.     timer.function = process_timeout;
  568.  
  569.     add_timer(&timer);
  570.     schedule();
  571.     del_timer(&timer);
  572.  
  573.     timeout = expire - jiffies;
  574.  
  575.  out:
  576.     return timeout < 0 ? 0 : timeout;
  577. }
  578.  
  579. /*
  580.  * This one aligns per-CPU data on cacheline boundaries.
  581.  */
  582. static union {
  583.     struct schedule_data {
  584.         struct task_struct * prev;
  585.         long prevstate;
  586.         cycles_t last_schedule;
  587.     } schedule_data;
  588.     char __pad [SMP_CACHE_BYTES];
  589. } aligned_data [NR_CPUS] __cacheline_aligned = { {{&init_task,0}}};
  590.  
  591.  
  592. static inline void __schedule_tail (void)
  593. {
  594. #ifdef __SMP__
  595.     struct schedule_data * sched_data;
  596.  
  597.     /*
  598.      * We might have switched CPUs:
  599.      */
  600.     sched_data = & aligned_data[smp_processor_id()].schedule_data;
  601.  
  602.     /*
  603.      * Subtle. In the rare event that we got a wakeup to 'prev' just
  604.      * during the reschedule (this is possible, the scheduler is pretty
  605.      * parallel), we should do another reschedule in the next task's
  606.      * context. schedule() will do the right thing next time around.
  607.      * this is equivalent to 'delaying' the wakeup until the reschedule
  608.      * has finished.
  609.      */
  610.     if (sched_data->prev->state != sched_data->prevstate)
  611.         current->need_resched = 1;
  612.  
  613.     /*
  614.      * Release the previous process ...
  615.      *
  616.      * We have dropped all locks, and we must make sure that we
  617.      * only mark the previous process as no longer having a CPU
  618.      * after all other state has been seen by other CPU's. Thus
  619.      * the write memory barrier!
  620.      */
  621.     wmb();
  622.     sched_data->prev->has_cpu = 0;
  623. #endif /* __SMP__ */
  624. }
  625.  
  626. /*
  627.  * schedule_tail() is getting called from the fork return path. This
  628.  * cleans up all remaining scheduler things, without impacting the
  629.  * common case.
  630.  */
  631. void schedule_tail (void)
  632. {
  633.     __schedule_tail();
  634. }
  635.  
  636. /*
  637.  *  'schedule()' is the scheduler function. It's a very simple and nice
  638.  * scheduler: it's not perfect, but certainly works for most things.
  639.  *
  640.  * The goto is "interesting".
  641.  *
  642.  *   NOTE!!  Task 0 is the 'idle' task, which gets called when no other
  643.  * tasks can run. It can not be killed, and it cannot sleep. The 'state'
  644.  * information in task[0] is never used.
  645.  */
  646. asmlinkage void schedule(void)
  647. {
  648.     struct schedule_data * sched_data;
  649.     struct task_struct * prev, * next;
  650.     int this_cpu;
  651.  
  652.     run_task_queue(&tq_scheduler);
  653.  
  654.     prev = current;
  655.     this_cpu = prev->processor;
  656.     /*
  657.      * 'sched_data' is protected by the fact that we can run
  658.      * only one process per CPU.
  659.      */
  660.     sched_data = & aligned_data[this_cpu].schedule_data;
  661.  
  662.     if (in_interrupt())
  663.         goto scheduling_in_interrupt;
  664.     release_kernel_lock(prev, this_cpu);
  665.  
  666.     /* Do "administrative" work here while we don't hold any locks */
  667.     if (bh_active & bh_mask)
  668.         do_bottom_half();
  669.  
  670.     spin_lock(&scheduler_lock);
  671.     spin_lock_irq(&runqueue_lock);
  672.  
  673.     /* move an exhausted RR process to be last.. */
  674.     prev->need_resched = 0;
  675.  
  676.     if (!prev->counter && prev->policy == SCHED_RR) {
  677.         prev->counter = prev->priority;
  678.         move_last_runqueue(prev);
  679.     }
  680.  
  681.     switch (prev->state) {
  682.         case TASK_INTERRUPTIBLE:
  683.             if (signal_pending(prev)) {
  684.                 prev->state = TASK_RUNNING;
  685.                 break;
  686.             }
  687.         default:
  688.             del_from_runqueue(prev);
  689.         case TASK_RUNNING:
  690.     }
  691.  
  692.     sched_data->prevstate = prev->state;
  693.  
  694. /* this is the scheduler proper: */
  695.     {
  696.         struct task_struct * p = init_task.next_run;
  697.         int c = -1000;
  698.  
  699.         /* Default process to select.. */
  700.         next = idle_task;
  701.         if (prev->state == TASK_RUNNING) {
  702.             c = goodness(prev, prev, this_cpu);
  703.             next = prev;
  704.         }
  705.  
  706.         /*
  707.          * This is subtle.
  708.          * Note how we can enable interrupts here, even
  709.          * though interrupts can add processes to the run-
  710.          * queue. This is because any new processes will
  711.          * be added to the front of the queue, so "p" above
  712.          * is a safe starting point.
  713.          * run-queue deletion and re-ordering is protected by
  714.          * the scheduler lock
  715.          */
  716.         spin_unlock_irq(&runqueue_lock);
  717. /*
  718.  * Note! there may appear new tasks on the run-queue during this, as
  719.  * interrupts are enabled. However, they will be put on front of the
  720.  * list, so our list starting at "p" is essentially fixed.
  721.  */
  722.         while (p != &init_task) {
  723.             if (can_schedule(p)) {
  724.                 int weight = goodness(p, prev, this_cpu);
  725.                 if (weight > c)
  726.                     c = weight, next = p;
  727.             }
  728.             p = p->next_run;
  729.         }
  730.  
  731.         /* Do we need to re-calculate counters? */
  732.         if (!c) {
  733.             struct task_struct *p;
  734.             read_lock(&tasklist_lock);
  735.             for_each_task(p)
  736.                 p->counter = (p->counter >> 1) + p->priority;
  737.             read_unlock(&tasklist_lock);
  738.         }
  739.     }
  740.  
  741.      /*
  742.       * maintain the per-process 'average timeslice' value.
  743.       * (this has to be recalculated even if we reschedule to
  744.       * the same process) Currently this is only used on SMP:
  745.       */
  746. #ifdef __SMP__
  747.     {
  748.         cycles_t t, this_slice;
  749.  
  750.         t = get_cycles();
  751.         this_slice = t - sched_data->last_schedule;
  752.         sched_data->last_schedule = t;
  753.  
  754.         /*
  755.          * Simple, exponentially fading average calculation:
  756.          */
  757.         prev->avg_slice = this_slice + prev->avg_slice;
  758.         prev->avg_slice >>= 1;
  759.     }
  760.  
  761.     /*
  762.      * We drop the scheduler lock early (it's a global spinlock),
  763.      * thus we have to lock the previous process from getting
  764.      * rescheduled during switch_to().
  765.      */
  766.      next->processor = this_cpu;
  767.      next->has_cpu = 1;
  768.     spin_unlock(&scheduler_lock);
  769. #endif /* __SMP__ */
  770.      if (prev != next) {
  771. #ifdef __SMP__
  772.         sched_data->prev = prev;
  773. #endif
  774.          kstat.context_swtch++;
  775.         get_mmu_context(next);
  776.         switch_to(prev,next);
  777.  
  778.         __schedule_tail();
  779.     }
  780.   
  781.     reacquire_kernel_lock(current);
  782.     return;
  783.  
  784. scheduling_in_interrupt:
  785.     printk("Scheduling in interrupt\n");
  786.     *(int *)0 = 0;
  787. }
  788.  
  789. rwlock_t waitqueue_lock = RW_LOCK_UNLOCKED;
  790.  
  791. /*
  792.  * wake_up doesn't wake up stopped processes - they have to be awakened
  793.  * with signals or similar.
  794.  *
  795.  * Note that we only need a read lock for the wait queue (and thus do not
  796.  * have to protect against interrupts), as the actual removal from the
  797.  * queue is handled by the process itself.
  798.  */
  799. void __wake_up(struct wait_queue **q, unsigned int mode)
  800. {
  801.     struct wait_queue *next;
  802.  
  803.     read_lock(&waitqueue_lock);
  804.     if (q && (next = *q)) {
  805.         struct wait_queue *head;
  806.  
  807.         head = WAIT_QUEUE_HEAD(q);
  808.         while (next != head) {
  809.             struct task_struct *p = next->task;
  810.             next = next->next;
  811.             if (p->state & mode)
  812.                 wake_up_process(p);
  813.         }
  814.     }
  815.     read_unlock(&waitqueue_lock);
  816. }
  817.  
  818. /*
  819.  * Semaphores are implemented using a two-way counter:
  820.  * The "count" variable is decremented for each process
  821.  * that tries to sleep, while the "waking" variable is
  822.  * incremented when the "up()" code goes to wake up waiting
  823.  * processes.
  824.  *
  825.  * Notably, the inline "up()" and "down()" functions can
  826.  * efficiently test if they need to do any extra work (up
  827.  * needs to do something only if count was negative before
  828.  * the increment operation.
  829.  *
  830.  * waking_non_zero() (from asm/semaphore.h) must execute
  831.  * atomically.
  832.  *
  833.  * When __up() is called, the count was negative before
  834.  * incrementing it, and we need to wake up somebody.
  835.  *
  836.  * This routine adds one to the count of processes that need to
  837.  * wake up and exit.  ALL waiting processes actually wake up but
  838.  * only the one that gets to the "waking" field first will gate
  839.  * through and acquire the semaphore.  The others will go back
  840.  * to sleep.
  841.  *
  842.  * Note that these functions are only called when there is
  843.  * contention on the lock, and as such all this is the
  844.  * "non-critical" part of the whole semaphore business. The
  845.  * critical part is the inline stuff in <asm/semaphore.h>
  846.  * where we want to avoid any extra jumps and calls.
  847.  */
  848. void __up(struct semaphore *sem)
  849. {
  850.     wake_one_more(sem);
  851.     wake_up(&sem->wait);
  852. }
  853.  
  854. /*
  855.  * Perform the "down" function.  Return zero for semaphore acquired,
  856.  * return negative for signalled out of the function.
  857.  *
  858.  * If called from __down, the return is ignored and the wait loop is
  859.  * not interruptible.  This means that a task waiting on a semaphore
  860.  * using "down()" cannot be killed until someone does an "up()" on
  861.  * the semaphore.
  862.  *
  863.  * If called from __down_interruptible, the return value gets checked
  864.  * upon return.  If the return value is negative then the task continues
  865.  * with the negative value in the return register (it can be tested by
  866.  * the caller).
  867.  *
  868.  * Either form may be used in conjunction with "up()".
  869.  *
  870.  */
  871.  
  872. #define DOWN_VAR                \
  873.     struct task_struct *tsk = current;    \
  874.     struct wait_queue wait = { tsk, NULL };
  875.  
  876. #define DOWN_HEAD(task_state)                        \
  877.                                     \
  878.                                     \
  879.     tsk->state = (task_state);                    \
  880.     add_wait_queue(&sem->wait, &wait);                \
  881.                                     \
  882.     /*                                \
  883.      * Ok, we're set up.  sem->count is known to be less than zero    \
  884.      * so we must wait.                        \
  885.      *                                \
  886.      * We can let go the lock for purposes of waiting.        \
  887.      * We re-acquire it after awaking so as to protect        \
  888.      * all semaphore operations.                    \
  889.      *                                \
  890.      * If "up()" is called before we call waking_non_zero() then    \
  891.      * we will catch it right away.  If it is called later then    \
  892.      * we will have to go through a wakeup cycle to catch it.    \
  893.      *                                \
  894.      * Multiple waiters contend for the semaphore lock to see    \
  895.      * who gets to gate through and who has to wait some more.    \
  896.      */                                \
  897.     for (;;) {
  898.  
  899. #define DOWN_TAIL(task_state)            \
  900.         tsk->state = (task_state);    \
  901.     }                    \
  902.     tsk->state = TASK_RUNNING;        \
  903.     remove_wait_queue(&sem->wait, &wait);
  904.  
  905. void __down(struct semaphore * sem)
  906. {
  907.     DOWN_VAR
  908.     DOWN_HEAD(TASK_UNINTERRUPTIBLE)
  909.     if (waking_non_zero(sem))
  910.         break;
  911.     schedule();
  912.     DOWN_TAIL(TASK_UNINTERRUPTIBLE)
  913. }
  914.  
  915. int __down_interruptible(struct semaphore * sem)
  916. {
  917.     DOWN_VAR
  918.     int ret = 0;
  919.     DOWN_HEAD(TASK_INTERRUPTIBLE)
  920.  
  921.     ret = waking_non_zero_interruptible(sem, tsk);
  922.     if (ret)
  923.     {
  924.         if (ret == 1)
  925.             /* ret != 0 only if we get interrupted -arca */
  926.             ret = 0;
  927.         break;
  928.     }
  929.     schedule();
  930.     DOWN_TAIL(TASK_INTERRUPTIBLE)
  931.     return ret;
  932. }
  933.  
  934. int __down_trylock(struct semaphore * sem)
  935. {
  936.     return waking_non_zero_trylock(sem);
  937. }
  938.  
  939. #define    SLEEP_ON_VAR                \
  940.     unsigned long flags;            \
  941.     struct wait_queue wait;
  942.  
  943. #define    SLEEP_ON_HEAD                    \
  944.     wait.task = current;                \
  945.     write_lock_irqsave(&waitqueue_lock, flags);    \
  946.     __add_wait_queue(p, &wait);            \
  947.     write_unlock(&waitqueue_lock);
  948.  
  949. #define    SLEEP_ON_TAIL                        \
  950.     write_lock_irq(&waitqueue_lock);            \
  951.     __remove_wait_queue(p, &wait);                \
  952.     write_unlock_irqrestore(&waitqueue_lock, flags);
  953.  
  954. void interruptible_sleep_on(struct wait_queue **p)
  955. {
  956.     SLEEP_ON_VAR
  957.  
  958.     current->state = TASK_INTERRUPTIBLE;
  959.  
  960.     SLEEP_ON_HEAD
  961.     schedule();
  962.     SLEEP_ON_TAIL
  963. }
  964.  
  965. long interruptible_sleep_on_timeout(struct wait_queue **p, long timeout)
  966. {
  967.     SLEEP_ON_VAR
  968.  
  969.     current->state = TASK_INTERRUPTIBLE;
  970.  
  971.     SLEEP_ON_HEAD
  972.     timeout = schedule_timeout(timeout);
  973.     SLEEP_ON_TAIL
  974.  
  975.     return timeout;
  976. }
  977.  
  978. void sleep_on(struct wait_queue **p)
  979. {
  980.     SLEEP_ON_VAR
  981.     
  982.     current->state = TASK_UNINTERRUPTIBLE;
  983.  
  984.     SLEEP_ON_HEAD
  985.     schedule();
  986.     SLEEP_ON_TAIL
  987. }
  988.  
  989. long sleep_on_timeout(struct wait_queue **p, long timeout)
  990. {
  991.     SLEEP_ON_VAR
  992.     
  993.     current->state = TASK_UNINTERRUPTIBLE;
  994.  
  995.     SLEEP_ON_HEAD
  996.     timeout = schedule_timeout(timeout);
  997.     SLEEP_ON_TAIL
  998.  
  999.     return timeout;
  1000. }
  1001.  
  1002. void scheduling_functions_end_here(void) { }
  1003.  
  1004. static inline void cascade_timers(struct timer_vec *tv)
  1005. {
  1006.         /* cascade all the timers from tv up one level */
  1007.         struct timer_list *timer;
  1008.         timer = tv->vec[tv->index];
  1009.         /*
  1010.          * We are removing _all_ timers from the list, so we don't  have to
  1011.          * detach them individually, just clear the list afterwards.
  1012.          */
  1013.         while (timer) {
  1014.                 struct timer_list *tmp = timer;
  1015.                 timer = timer->next;
  1016.                 internal_add_timer(tmp);
  1017.         }
  1018.         tv->vec[tv->index] = NULL;
  1019.         tv->index = (tv->index + 1) & TVN_MASK;
  1020. }
  1021.  
  1022. static inline void run_timer_list(void)
  1023. {
  1024.     spin_lock_irq(&timerlist_lock);
  1025.     while ((long)(jiffies - timer_jiffies) >= 0) {
  1026.         struct timer_list *timer;
  1027.         if (!tv1.index) {
  1028.             int n = 1;
  1029.             do {
  1030.                 cascade_timers(tvecs[n]);
  1031.             } while (tvecs[n]->index == 1 && ++n < NOOF_TVECS);
  1032.         }
  1033.         while ((timer = tv1.vec[tv1.index])) {
  1034.             void (*fn)(unsigned long) = timer->function;
  1035.             unsigned long data = timer->data;
  1036.             detach_timer(timer);
  1037.             timer->next = timer->prev = NULL;
  1038.             spin_unlock_irq(&timerlist_lock);
  1039.             fn(data);
  1040.             spin_lock_irq(&timerlist_lock);
  1041.         }
  1042.         ++timer_jiffies; 
  1043.         tv1.index = (tv1.index + 1) & TVR_MASK;
  1044.     }
  1045.     spin_unlock_irq(&timerlist_lock);
  1046. }
  1047.  
  1048.  
  1049. static inline void run_old_timers(void)
  1050. {
  1051.     struct timer_struct *tp;
  1052.     unsigned long mask;
  1053.  
  1054.     for (mask = 1, tp = timer_table+0 ; mask ; tp++,mask += mask) {
  1055.         if (mask > timer_active)
  1056.             break;
  1057.         if (!(mask & timer_active))
  1058.             continue;
  1059.         if (time_after(tp->expires, jiffies))
  1060.             continue;
  1061.         timer_active &= ~mask;
  1062.         tp->fn();
  1063.         sti();
  1064.     }
  1065. }
  1066.  
  1067. spinlock_t tqueue_lock;
  1068.  
  1069. void tqueue_bh(void)
  1070. {
  1071.     run_task_queue(&tq_timer);
  1072. }
  1073.  
  1074. void immediate_bh(void)
  1075. {
  1076.     run_task_queue(&tq_immediate);
  1077. }
  1078.  
  1079. unsigned long timer_active = 0;
  1080. struct timer_struct timer_table[32];
  1081.  
  1082. /*
  1083.  * Hmm.. Changed this, as the GNU make sources (load.c) seems to
  1084.  * imply that avenrun[] is the standard name for this kind of thing.
  1085.  * Nothing else seems to be standardized: the fractional size etc
  1086.  * all seem to differ on different machines.
  1087.  */
  1088. unsigned long avenrun[3] = { 0,0,0 };
  1089.  
  1090. /*
  1091.  * Nr of active tasks - counted in fixed-point numbers
  1092.  */
  1093. static unsigned long count_active_tasks(void)
  1094. {
  1095.     struct task_struct *p;
  1096.     unsigned long nr = 0;
  1097.  
  1098.     read_lock(&tasklist_lock);
  1099.     for_each_task(p) {
  1100.         if ((p->state == TASK_RUNNING ||
  1101.              p->state == TASK_UNINTERRUPTIBLE ||
  1102.              p->state == TASK_SWAPPING))
  1103.             nr += FIXED_1;
  1104.     }
  1105.     read_unlock(&tasklist_lock);
  1106.     return nr;
  1107. }
  1108.  
  1109. static inline void calc_load(unsigned long ticks)
  1110. {
  1111.     unsigned long active_tasks; /* fixed-point */
  1112.     static int count = LOAD_FREQ;
  1113.  
  1114.     count -= ticks;
  1115.     if (count < 0) {
  1116.         count += LOAD_FREQ;
  1117.         active_tasks = count_active_tasks();
  1118.         CALC_LOAD(avenrun[0], EXP_1, active_tasks);
  1119.         CALC_LOAD(avenrun[1], EXP_5, active_tasks);
  1120.         CALC_LOAD(avenrun[2], EXP_15, active_tasks);
  1121.     }
  1122. }
  1123.  
  1124. /*
  1125.  * this routine handles the overflow of the microsecond field
  1126.  *
  1127.  * The tricky bits of code to handle the accurate clock support
  1128.  * were provided by Dave Mills (Mills@UDEL.EDU) of NTP fame.
  1129.  * They were originally developed for SUN and DEC kernels.
  1130.  * All the kudos should go to Dave for this stuff.
  1131.  *
  1132.  */
  1133. static void second_overflow(void)
  1134. {
  1135.     long ltemp;
  1136.  
  1137.     /* Bump the maxerror field */
  1138.     time_maxerror += time_tolerance >> SHIFT_USEC;
  1139.     if ( time_maxerror > NTP_PHASE_LIMIT ) {
  1140.         time_maxerror = NTP_PHASE_LIMIT;
  1141.     time_status |= STA_UNSYNC;
  1142.     }
  1143.  
  1144.     /*
  1145.      * Leap second processing. If in leap-insert state at
  1146.      * the end of the day, the system clock is set back one
  1147.      * second; if in leap-delete state, the system clock is
  1148.      * set ahead one second. The microtime() routine or
  1149.      * external clock driver will insure that reported time
  1150.      * is always monotonic. The ugly divides should be
  1151.      * replaced.
  1152.      */
  1153.     switch (time_state) {
  1154.  
  1155.     case TIME_OK:
  1156.     if (time_status & STA_INS)
  1157.         time_state = TIME_INS;
  1158.     else if (time_status & STA_DEL)
  1159.         time_state = TIME_DEL;
  1160.     break;
  1161.  
  1162.     case TIME_INS:
  1163.     if (xtime.tv_sec % 86400 == 0) {
  1164.         xtime.tv_sec--;
  1165.         time_state = TIME_OOP;
  1166.         printk(KERN_NOTICE "Clock: inserting leap second 23:59:60 UTC\n");
  1167.     }
  1168.     break;
  1169.  
  1170.     case TIME_DEL:
  1171.     if ((xtime.tv_sec + 1) % 86400 == 0) {
  1172.         xtime.tv_sec++;
  1173.         time_state = TIME_WAIT;
  1174.         printk(KERN_NOTICE "Clock: deleting leap second 23:59:59 UTC\n");
  1175.     }
  1176.     break;
  1177.  
  1178.     case TIME_OOP:
  1179.     time_state = TIME_WAIT;
  1180.     break;
  1181.  
  1182.     case TIME_WAIT:
  1183.     if (!(time_status & (STA_INS | STA_DEL)))
  1184.         time_state = TIME_OK;
  1185.     }
  1186.  
  1187.     /*
  1188.      * Compute the phase adjustment for the next second. In
  1189.      * PLL mode, the offset is reduced by a fixed factor
  1190.      * times the time constant. In FLL mode the offset is
  1191.      * used directly. In either mode, the maximum phase
  1192.      * adjustment for each second is clamped so as to spread
  1193.      * the adjustment over not more than the number of
  1194.      * seconds between updates.
  1195.      */
  1196.     if (time_offset < 0) {
  1197.     ltemp = -time_offset;
  1198.     if (!(time_status & STA_FLL))
  1199.         ltemp >>= SHIFT_KG + time_constant;
  1200.     if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
  1201.         ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;
  1202.     time_offset += ltemp;
  1203.     time_adj = -ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
  1204.     } else {
  1205.     ltemp = time_offset;
  1206.     if (!(time_status & STA_FLL))
  1207.         ltemp >>= SHIFT_KG + time_constant;
  1208.     if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
  1209.         ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;
  1210.     time_offset -= ltemp;
  1211.     time_adj = ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
  1212.     }
  1213.  
  1214.     /*
  1215.      * Compute the frequency estimate and additional phase
  1216.      * adjustment due to frequency error for the next
  1217.      * second. When the PPS signal is engaged, gnaw on the
  1218.      * watchdog counter and update the frequency computed by
  1219.      * the pll and the PPS signal.
  1220.      */
  1221.     pps_valid++;
  1222.     if (pps_valid == PPS_VALID) {    /* PPS signal lost */
  1223.     pps_jitter = MAXTIME;
  1224.     pps_stabil = MAXFREQ;
  1225.     time_status &= ~(STA_PPSSIGNAL | STA_PPSJITTER |
  1226.              STA_PPSWANDER | STA_PPSERROR);
  1227.     }
  1228.     ltemp = time_freq + pps_freq;
  1229.     if (ltemp < 0)
  1230.     time_adj -= -ltemp >>
  1231.         (SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE);
  1232.     else
  1233.     time_adj += ltemp >>
  1234.         (SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE);
  1235.  
  1236. #if HZ == 100
  1237.     /* Compensate for (HZ==100) != (1 << SHIFT_HZ).
  1238.      * Add 25% and 3.125% to get 128.125; => only 0.125% error (p. 14)
  1239.      */
  1240.     if (time_adj < 0)
  1241.     time_adj -= (-time_adj >> 2) + (-time_adj >> 5);
  1242.     else
  1243.     time_adj += (time_adj >> 2) + (time_adj >> 5);
  1244. #endif
  1245. }
  1246.  
  1247. /* in the NTP reference this is called "hardclock()" */
  1248. static void update_wall_time_one_tick(void)
  1249. {
  1250.     if ( (time_adjust_step = time_adjust) != 0 ) {
  1251.         /* We are doing an adjtime thing. 
  1252.          *
  1253.          * Prepare time_adjust_step to be within bounds.
  1254.          * Note that a positive time_adjust means we want the clock
  1255.          * to run faster.
  1256.          *
  1257.          * Limit the amount of the step to be in the range
  1258.          * -tickadj .. +tickadj
  1259.          */
  1260.          if (time_adjust > tickadj)
  1261.         time_adjust_step = tickadj;
  1262.          else if (time_adjust < -tickadj)
  1263.         time_adjust_step = -tickadj;
  1264.          
  1265.         /* Reduce by this step the amount of time left  */
  1266.         time_adjust -= time_adjust_step;
  1267.     }
  1268.     xtime.tv_usec += tick + time_adjust_step;
  1269.     /*
  1270.      * Advance the phase, once it gets to one microsecond, then
  1271.      * advance the tick more.
  1272.      */
  1273.     time_phase += time_adj;
  1274.     if (time_phase <= -FINEUSEC) {
  1275.         long ltemp = -time_phase >> SHIFT_SCALE;
  1276.         time_phase += ltemp << SHIFT_SCALE;
  1277.         xtime.tv_usec -= ltemp;
  1278.     }
  1279.     else if (time_phase >= FINEUSEC) {
  1280.         long ltemp = time_phase >> SHIFT_SCALE;
  1281.         time_phase -= ltemp << SHIFT_SCALE;
  1282.         xtime.tv_usec += ltemp;
  1283.     }
  1284. }
  1285.  
  1286. /*
  1287.  * Using a loop looks inefficient, but "ticks" is
  1288.  * usually just one (we shouldn't be losing ticks,
  1289.  * we're doing this this way mainly for interrupt
  1290.  * latency reasons, not because we think we'll
  1291.  * have lots of lost timer ticks
  1292.  */
  1293. static void update_wall_time(unsigned long ticks)
  1294. {
  1295.     do {
  1296.         ticks--;
  1297.         update_wall_time_one_tick();
  1298.     } while (ticks);
  1299.  
  1300.     if (xtime.tv_usec >= 1000000) {
  1301.         xtime.tv_usec -= 1000000;
  1302.         xtime.tv_sec++;
  1303.         second_overflow();
  1304.     }
  1305. }
  1306.  
  1307. static inline void do_process_times(struct task_struct *p,
  1308.     unsigned long user, unsigned long system)
  1309. {
  1310.     long psecs;
  1311.  
  1312.     psecs = (p->times.tms_utime += user);
  1313.     psecs += (p->times.tms_stime += system);
  1314.     if (psecs / HZ > p->rlim[RLIMIT_CPU].rlim_cur) {
  1315.         /* Send SIGXCPU every second.. */
  1316.         if (!(psecs % HZ))
  1317.             send_sig(SIGXCPU, p, 1);
  1318.         /* and SIGKILL when we go over max.. */
  1319.         if (psecs / HZ > p->rlim[RLIMIT_CPU].rlim_max)
  1320.             send_sig(SIGKILL, p, 1);
  1321.     }
  1322. }
  1323.  
  1324. static inline void do_it_virt(struct task_struct * p, unsigned long ticks)
  1325. {
  1326.     unsigned long it_virt = p->it_virt_value;
  1327.  
  1328.     if (it_virt) {
  1329.         if (it_virt <= ticks) {
  1330.             it_virt = ticks + p->it_virt_incr;
  1331.             send_sig(SIGVTALRM, p, 1);
  1332.         }
  1333.         p->it_virt_value = it_virt - ticks;
  1334.     }
  1335. }
  1336.  
  1337. static inline void do_it_prof(struct task_struct * p, unsigned long ticks)
  1338. {
  1339.     unsigned long it_prof = p->it_prof_value;
  1340.  
  1341.     if (it_prof) {
  1342.         if (it_prof <= ticks) {
  1343.             it_prof = ticks + p->it_prof_incr;
  1344.             send_sig(SIGPROF, p, 1);
  1345.         }
  1346.         p->it_prof_value = it_prof - ticks;
  1347.     }
  1348. }
  1349.  
  1350. void update_one_process(struct task_struct *p,
  1351.     unsigned long ticks, unsigned long user, unsigned long system, int cpu)
  1352. {
  1353.     p->per_cpu_utime[cpu] += user;
  1354.     p->per_cpu_stime[cpu] += system;
  1355.     do_process_times(p, user, system);
  1356.     do_it_virt(p, user);
  1357.     do_it_prof(p, ticks);
  1358. }    
  1359.  
  1360. static void update_process_times(unsigned long ticks, unsigned long system)
  1361. {
  1362. /*
  1363.  * SMP does this on a per-CPU basis elsewhere
  1364.  */
  1365. #ifndef  __SMP__
  1366.     struct task_struct * p = current;
  1367.     unsigned long user = ticks - system;
  1368.     if (p->pid) {
  1369.         p->counter -= ticks;
  1370.         if (p->counter < 0) {
  1371.             p->counter = 0;
  1372.             p->need_resched = 1;
  1373.         }
  1374.         if (p->priority < DEF_PRIORITY)
  1375.             kstat.cpu_nice += user;
  1376.         else
  1377.             kstat.cpu_user += user;
  1378.         kstat.cpu_system += system;
  1379.     }
  1380.     update_one_process(p, ticks, user, system, 0);
  1381. #endif
  1382. }
  1383.  
  1384. volatile unsigned long lost_ticks = 0;
  1385. static unsigned long lost_ticks_system = 0;
  1386.  
  1387. /*
  1388.  * This spinlock protect us from races in SMP while playing with xtime. -arca
  1389.  */
  1390. rwlock_t xtime_lock = RW_LOCK_UNLOCKED;
  1391.  
  1392. static inline void update_times(void)
  1393. {
  1394.     unsigned long ticks;
  1395.  
  1396.     /*
  1397.      * update_times() is run from the raw timer_bh handler so we
  1398.      * just know that the irqs are locally enabled and so we don't
  1399.      * need to save/restore the flags of the local CPU here. -arca
  1400.      */
  1401.     write_lock_irq(&xtime_lock);
  1402.  
  1403.     ticks = lost_ticks;
  1404.     lost_ticks = 0;
  1405.  
  1406.     if (ticks) {
  1407.         unsigned long system;
  1408.         system = xchg(&lost_ticks_system, 0);
  1409.  
  1410.         calc_load(ticks);
  1411.         update_wall_time(ticks);
  1412.         write_unlock_irq(&xtime_lock);
  1413.         
  1414.         update_process_times(ticks, system);
  1415.  
  1416.     } else
  1417.         write_unlock_irq(&xtime_lock);
  1418. }
  1419.  
  1420. static void timer_bh(void)
  1421. {
  1422.     update_times();
  1423.     run_old_timers();
  1424.     run_timer_list();
  1425. }
  1426.  
  1427. void do_timer(struct pt_regs * regs)
  1428. {
  1429.     (*(unsigned long *)&jiffies)++;
  1430.     lost_ticks++;
  1431.     mark_bh(TIMER_BH);
  1432.     if (!user_mode(regs))
  1433.         lost_ticks_system++;
  1434.     if (tq_timer)
  1435.         mark_bh(TQUEUE_BH);
  1436. }
  1437.  
  1438. #ifndef __alpha__
  1439.  
  1440. /*
  1441.  * For backwards compatibility?  This can be done in libc so Alpha
  1442.  * and all newer ports shouldn't need it.
  1443.  */
  1444. asmlinkage unsigned int sys_alarm(unsigned int seconds)
  1445. {
  1446.     struct itimerval it_new, it_old;
  1447.     unsigned int oldalarm;
  1448.  
  1449.     it_new.it_interval.tv_sec = it_new.it_interval.tv_usec = 0;
  1450.     it_new.it_value.tv_sec = seconds;
  1451.     it_new.it_value.tv_usec = 0;
  1452.     do_setitimer(ITIMER_REAL, &it_new, &it_old);
  1453.     oldalarm = it_old.it_value.tv_sec;
  1454.     /* ehhh.. We can't return 0 if we have an alarm pending.. */
  1455.     /* And we'd better return too much than too little anyway */
  1456.     if (it_old.it_value.tv_usec)
  1457.         oldalarm++;
  1458.     return oldalarm;
  1459. }
  1460.  
  1461. /*
  1462.  * The Alpha uses getxpid, getxuid, and getxgid instead.  Maybe this
  1463.  * should be moved into arch/i386 instead?
  1464.  */
  1465.  
  1466. asmlinkage int sys_getpid(void)
  1467. {
  1468.     /* This is SMP safe - current->pid doesn't change */
  1469.     return current->pid;
  1470. }
  1471.  
  1472. /*
  1473.  * This is not strictly SMP safe: p_opptr could change
  1474.  * from under us. However, rather than getting any lock
  1475.  * we can use an optimistic algorithm: get the parent
  1476.  * pid, and go back and check that the parent is still
  1477.  * the same. If it has changed (which is extremely unlikely
  1478.  * indeed), we just try again..
  1479.  *
  1480.  * NOTE! This depends on the fact that even if we _do_
  1481.  * get an old value of "parent", we can happily dereference
  1482.  * the pointer: we just can't necessarily trust the result
  1483.  * until we know that the parent pointer is valid.
  1484.  *
  1485.  * The "mb()" macro is a memory barrier - a synchronizing
  1486.  * event. It also makes sure that gcc doesn't optimize
  1487.  * away the necessary memory references.. The barrier doesn't
  1488.  * have to have all that strong semantics: on x86 we don't
  1489.  * really require a synchronizing instruction, for example.
  1490.  * The barrier is more important for code generation than
  1491.  * for any real memory ordering semantics (even if there is
  1492.  * a small window for a race, using the old pointer is
  1493.  * harmless for a while).
  1494.  */
  1495. asmlinkage int sys_getppid(void)
  1496. {
  1497.     int pid;
  1498.     struct task_struct * me = current;
  1499.     struct task_struct * parent;
  1500.  
  1501.     parent = me->p_opptr;
  1502.     for (;;) {
  1503.         pid = parent->pid;
  1504. #if __SMP__
  1505. {
  1506.         struct task_struct *old = parent;
  1507.         mb();
  1508.         parent = me->p_opptr;
  1509.         if (old != parent)
  1510.             continue;
  1511. }
  1512. #endif
  1513.         break;
  1514.     }
  1515.     return pid;
  1516. }
  1517.  
  1518. asmlinkage int sys_getuid(void)
  1519. {
  1520.     /* Only we change this so SMP safe */
  1521.     return current->uid;
  1522. }
  1523.  
  1524. asmlinkage int sys_geteuid(void)
  1525. {
  1526.     /* Only we change this so SMP safe */
  1527.     return current->euid;
  1528. }
  1529.  
  1530. asmlinkage int sys_getgid(void)
  1531. {
  1532.     /* Only we change this so SMP safe */
  1533.     return current->gid;
  1534. }
  1535.  
  1536. asmlinkage int sys_getegid(void)
  1537. {
  1538.     /* Only we change this so SMP safe */
  1539.     return  current->egid;
  1540. }
  1541.  
  1542. /*
  1543.  * This has been replaced by sys_setpriority.  Maybe it should be
  1544.  * moved into the arch dependent tree for those ports that require
  1545.  * it for backward compatibility?
  1546.  */
  1547.  
  1548. asmlinkage int sys_nice(int increment)
  1549. {
  1550.     unsigned long newprio;
  1551.     int increase = 0;
  1552.  
  1553.     /*
  1554.      *    Setpriority might change our priority at the same moment.
  1555.      *    We don't have to worry. Conceptually one call occurs first
  1556.      *    and we have a single winner.
  1557.      */
  1558.      
  1559.     newprio = increment;
  1560.     if (increment < 0) {
  1561.         if (!capable(CAP_SYS_NICE))
  1562.             return -EPERM;
  1563.         newprio = -increment;
  1564.         increase = 1;
  1565.     }
  1566.  
  1567.     if (newprio > 40)
  1568.         newprio = 40;
  1569.     /*
  1570.      * do a "normalization" of the priority (traditionally
  1571.      * Unix nice values are -20 to 20; Linux doesn't really
  1572.      * use that kind of thing, but uses the length of the
  1573.      * timeslice instead (default 210 ms). The rounding is
  1574.      * why we want to avoid negative values.
  1575.      */
  1576.     newprio = (newprio * DEF_PRIORITY + 10) / 20;
  1577.     increment = newprio;
  1578.     if (increase)
  1579.         increment = -increment;
  1580.     /*
  1581.      *    Current->priority can change between this point
  1582.      *    and the assignment. We are assigning not doing add/subs
  1583.      *    so thats ok. Conceptually a process might just instantaneously
  1584.      *    read the value we stomp over. I don't think that is an issue
  1585.      *    unless posix makes it one. If so we can loop on changes
  1586.      *    to current->priority.
  1587.      */
  1588.     newprio = current->priority - increment;
  1589.     if ((signed) newprio < 1)
  1590.         newprio = 1;
  1591.     if (newprio > DEF_PRIORITY*2)
  1592.         newprio = DEF_PRIORITY*2;
  1593.     current->priority = newprio;
  1594.     return 0;
  1595. }
  1596.  
  1597. #endif
  1598.  
  1599. static inline struct task_struct *find_process_by_pid(pid_t pid)
  1600. {
  1601.     struct task_struct *tsk = current;
  1602.  
  1603.     if (pid)
  1604.         tsk = find_task_by_pid(pid);
  1605.     return tsk;
  1606. }
  1607.  
  1608. static int setscheduler(pid_t pid, int policy, 
  1609.             struct sched_param *param)
  1610. {
  1611.     struct sched_param lp;
  1612.     struct task_struct *p;
  1613.     int retval;
  1614.  
  1615.     retval = -EINVAL;
  1616.     if (!param || pid < 0)
  1617.         goto out_nounlock;
  1618.  
  1619.     retval = -EFAULT;
  1620.     if (copy_from_user(&lp, param, sizeof(struct sched_param)))
  1621.         goto out_nounlock;
  1622.  
  1623.     /*
  1624.      * We play safe to avoid deadlocks.
  1625.      */
  1626.     spin_lock(&scheduler_lock);
  1627.     spin_lock_irq(&runqueue_lock);
  1628.     read_lock(&tasklist_lock);
  1629.  
  1630.     p = find_process_by_pid(pid);
  1631.  
  1632.     retval = -ESRCH;
  1633.     if (!p)
  1634.         goto out_unlock;
  1635.             
  1636.     if (policy < 0)
  1637.         policy = p->policy;
  1638.     else {
  1639.         retval = -EINVAL;
  1640.         if (policy != SCHED_FIFO && policy != SCHED_RR &&
  1641.                 policy != SCHED_OTHER)
  1642.             goto out_unlock;
  1643.     }
  1644.     
  1645.     /*
  1646.      * Valid priorities for SCHED_FIFO and SCHED_RR are 1..99, valid
  1647.      * priority for SCHED_OTHER is 0.
  1648.      */
  1649.     retval = -EINVAL;
  1650.     if (lp.sched_priority < 0 || lp.sched_priority > 99)
  1651.         goto out_unlock;
  1652.     if ((policy == SCHED_OTHER) != (lp.sched_priority == 0))
  1653.         goto out_unlock;
  1654.  
  1655.     retval = -EPERM;
  1656.     if ((policy == SCHED_FIFO || policy == SCHED_RR) && 
  1657.         !capable(CAP_SYS_NICE))
  1658.         goto out_unlock;
  1659.     if ((current->euid != p->euid) && (current->euid != p->uid) &&
  1660.         !capable(CAP_SYS_NICE))
  1661.         goto out_unlock;
  1662.  
  1663.     retval = 0;
  1664.     p->policy = policy;
  1665.     p->rt_priority = lp.sched_priority;
  1666.     if (p->next_run)
  1667.         move_first_runqueue(p);
  1668.  
  1669.     current->need_resched = 1;
  1670.  
  1671. out_unlock:
  1672.     read_unlock(&tasklist_lock);
  1673.     spin_unlock_irq(&runqueue_lock);
  1674.     spin_unlock(&scheduler_lock);
  1675.  
  1676. out_nounlock:
  1677.     return retval;
  1678. }
  1679.  
  1680. asmlinkage int sys_sched_setscheduler(pid_t pid, int policy, 
  1681.                       struct sched_param *param)
  1682. {
  1683.     return setscheduler(pid, policy, param);
  1684. }
  1685.  
  1686. asmlinkage int sys_sched_setparam(pid_t pid, struct sched_param *param)
  1687. {
  1688.     return setscheduler(pid, -1, param);
  1689. }
  1690.  
  1691. asmlinkage int sys_sched_getscheduler(pid_t pid)
  1692. {
  1693.     struct task_struct *p;
  1694.     int retval;
  1695.  
  1696.     retval = -EINVAL;
  1697.     if (pid < 0)
  1698.         goto out_nounlock;
  1699.  
  1700.     read_lock(&tasklist_lock);
  1701.  
  1702.     retval = -ESRCH;
  1703.     p = find_process_by_pid(pid);
  1704.     if (!p)
  1705.         goto out_unlock;
  1706.             
  1707.     retval = p->policy;
  1708.  
  1709. out_unlock:
  1710.     read_unlock(&tasklist_lock);
  1711.  
  1712. out_nounlock:
  1713.     return retval;
  1714. }
  1715.  
  1716. asmlinkage int sys_sched_getparam(pid_t pid, struct sched_param *param)
  1717. {
  1718.     struct task_struct *p;
  1719.     struct sched_param lp;
  1720.     int retval;
  1721.  
  1722.     retval = -EINVAL;
  1723.     if (!param || pid < 0)
  1724.         goto out_nounlock;
  1725.  
  1726.     read_lock(&tasklist_lock);
  1727.     p = find_process_by_pid(pid);
  1728.     retval = -ESRCH;
  1729.     if (!p)
  1730.         goto out_unlock;
  1731.     lp.sched_priority = p->rt_priority;
  1732.     read_unlock(&tasklist_lock);
  1733.  
  1734.     /*
  1735.      * This one might sleep, we cannot do it with a spinlock held ...
  1736.      */
  1737.     retval = copy_to_user(param, &lp, sizeof(*param)) ? -EFAULT : 0;
  1738.  
  1739. out_nounlock:
  1740.     return retval;
  1741.  
  1742. out_unlock:
  1743.     read_unlock(&tasklist_lock);
  1744.     return retval;
  1745. }
  1746.  
  1747. asmlinkage int sys_sched_yield(void)
  1748. {
  1749.     spin_lock(&scheduler_lock);
  1750.     spin_lock_irq(&runqueue_lock);
  1751.     if (current->policy == SCHED_OTHER)
  1752.         current->policy |= SCHED_YIELD;
  1753.     current->need_resched = 1;
  1754.     move_last_runqueue(current);
  1755.     spin_unlock_irq(&runqueue_lock);
  1756.     spin_unlock(&scheduler_lock);
  1757.     return 0;
  1758. }
  1759.  
  1760. asmlinkage int sys_sched_get_priority_max(int policy)
  1761. {
  1762.     int ret = -EINVAL;
  1763.  
  1764.     switch (policy) {
  1765.     case SCHED_FIFO:
  1766.     case SCHED_RR:
  1767.         ret = 99;
  1768.         break;
  1769.     case SCHED_OTHER:
  1770.         ret = 0;
  1771.         break;
  1772.     }
  1773.     return ret;
  1774. }
  1775.  
  1776. asmlinkage int sys_sched_get_priority_min(int policy)
  1777. {
  1778.     int ret = -EINVAL;
  1779.  
  1780.     switch (policy) {
  1781.     case SCHED_FIFO:
  1782.     case SCHED_RR:
  1783.         ret = 1;
  1784.         break;
  1785.     case SCHED_OTHER:
  1786.         ret = 0;
  1787.     }
  1788.     return ret;
  1789. }
  1790.  
  1791. asmlinkage int sys_sched_rr_get_interval(pid_t pid, struct timespec *interval)
  1792. {
  1793.     struct timespec t;
  1794.  
  1795.     t.tv_sec = 0;
  1796.     t.tv_nsec = 150000;
  1797.     if (copy_to_user(interval, &t, sizeof(struct timespec)))
  1798.         return -EFAULT;
  1799.     return 0;
  1800. }
  1801.  
  1802. asmlinkage int sys_nanosleep(struct timespec *rqtp, struct timespec *rmtp)
  1803. {
  1804.     struct timespec t;
  1805.     unsigned long expire;
  1806.  
  1807.     if(copy_from_user(&t, rqtp, sizeof(struct timespec)))
  1808.         return -EFAULT;
  1809.  
  1810.     if (t.tv_nsec >= 1000000000L || t.tv_nsec < 0 || t.tv_sec < 0)
  1811.         return -EINVAL;
  1812.  
  1813.  
  1814.     if (t.tv_sec == 0 && t.tv_nsec <= 2000000L &&
  1815.         current->policy != SCHED_OTHER)
  1816.     {
  1817.         /*
  1818.          * Short delay requests up to 2 ms will be handled with
  1819.          * high precision by a busy wait for all real-time processes.
  1820.          *
  1821.          * Its important on SMP not to do this holding locks.
  1822.          */
  1823.         udelay((t.tv_nsec + 999) / 1000);
  1824.         return 0;
  1825.     }
  1826.  
  1827.     expire = timespec_to_jiffies(&t) + (t.tv_sec || t.tv_nsec);
  1828.  
  1829.     current->state = TASK_INTERRUPTIBLE;
  1830.     expire = schedule_timeout(expire);
  1831.  
  1832.     if (expire) {
  1833.         if (rmtp) {
  1834.             jiffies_to_timespec(expire, &t);
  1835.             if (copy_to_user(rmtp, &t, sizeof(struct timespec)))
  1836.                 return -EFAULT;
  1837.         }
  1838.         return -EINTR;
  1839.     }
  1840.     return 0;
  1841. }
  1842.  
  1843. static void show_task(int nr,struct task_struct * p)
  1844. {
  1845.     unsigned long free = 0;
  1846.     int state;
  1847.     static const char * stat_nam[] = { "R", "S", "D", "Z", "T", "W" };
  1848.  
  1849.     printk("%-8s %3d ", p->comm, (p == current) ? -nr : nr);
  1850.     state = p->state ? ffz(~p->state) + 1 : 0;
  1851.     if (((unsigned) state) < sizeof(stat_nam)/sizeof(char *))
  1852.         printk(stat_nam[state]);
  1853.     else
  1854.         printk(" ");
  1855. #if (BITS_PER_LONG == 32)
  1856.     if (p == current)
  1857.         printk(" current  ");
  1858.     else
  1859.         printk(" %08lX ", thread_saved_pc(&p->tss));
  1860. #else
  1861.     if (p == current)
  1862.         printk("   current task   ");
  1863.     else
  1864.         printk(" %016lx ", thread_saved_pc(&p->tss));
  1865. #endif
  1866.     {
  1867.         unsigned long * n = (unsigned long *) (p+1);
  1868.         while (!*n)
  1869.             n++;
  1870.         free = (unsigned long) n - (unsigned long)(p+1);
  1871.     }
  1872.     printk("%5lu %5d %6d ", free, p->pid, p->p_pptr->pid);
  1873.     if (p->p_cptr)
  1874.         printk("%5d ", p->p_cptr->pid);
  1875.     else
  1876.         printk("      ");
  1877.     if (p->p_ysptr)
  1878.         printk("%7d", p->p_ysptr->pid);
  1879.     else
  1880.         printk("       ");
  1881.     if (p->p_osptr)
  1882.         printk(" %5d\n", p->p_osptr->pid);
  1883.     else
  1884.         printk("\n");
  1885.  
  1886.     {
  1887.         struct signal_queue *q;
  1888.         char s[sizeof(sigset_t)*2+1], b[sizeof(sigset_t)*2+1]; 
  1889.  
  1890.         render_sigset_t(&p->signal, s);
  1891.         render_sigset_t(&p->blocked, b);
  1892.         printk("   sig: %d %s %s :", signal_pending(p), s, b);
  1893.         for (q = p->sigqueue; q ; q = q->next)
  1894.             printk(" %d", q->info.si_signo);
  1895.         printk(" X\n");
  1896.     }
  1897. }
  1898.  
  1899. char * render_sigset_t(sigset_t *set, char *buffer)
  1900. {
  1901.     int i = _NSIG, x;
  1902.     do {
  1903.         i -= 4, x = 0;
  1904.         if (sigismember(set, i+1)) x |= 1;
  1905.         if (sigismember(set, i+2)) x |= 2;
  1906.         if (sigismember(set, i+3)) x |= 4;
  1907.         if (sigismember(set, i+4)) x |= 8;
  1908.         *buffer++ = (x < 10 ? '0' : 'a' - 10) + x;
  1909.     } while (i >= 4);
  1910.     *buffer = 0;
  1911.     return buffer;
  1912. }
  1913.  
  1914. void show_state(void)
  1915. {
  1916.     struct task_struct *p;
  1917.  
  1918. #if (BITS_PER_LONG == 32)
  1919.     printk("\n"
  1920.            "                         free                        sibling\n");
  1921.     printk("  task             PC    stack   pid father child younger older\n");
  1922. #else
  1923.     printk("\n"
  1924.            "                                 free                        sibling\n");
  1925.     printk("  task                 PC        stack   pid father child younger older\n");
  1926. #endif
  1927.     read_lock(&tasklist_lock);
  1928.     for_each_task(p)
  1929.         show_task((p->tarray_ptr - &task[0]),p);
  1930.     read_unlock(&tasklist_lock);
  1931. }
  1932.  
  1933. void __init sched_init(void)
  1934. {
  1935.     /*
  1936.      *    We have to do a little magic to get the first
  1937.      *    process right in SMP mode.
  1938.      */
  1939.     int cpu=hard_smp_processor_id();
  1940.     int nr = NR_TASKS;
  1941.  
  1942.     init_task.processor=cpu;
  1943.  
  1944.     /* Init task array free list and pidhash table. */
  1945.     while(--nr > 0)
  1946.         add_free_taskslot(&task[nr]);
  1947.  
  1948.     for(nr = 0; nr < PIDHASH_SZ; nr++)
  1949.         pidhash[nr] = NULL;
  1950.  
  1951.     init_bh(TIMER_BH, timer_bh);
  1952.     init_bh(TQUEUE_BH, tqueue_bh);
  1953.     init_bh(IMMEDIATE_BH, immediate_bh);
  1954. }
  1955.